#include "binaryTree.h"
#include <iostream>
#include <stdlib.h>
/*构造函数*/
BinaryTree::BinaryTree(int (*compareFunc)(ELEMENT_TYPE arg1, ELEMENT_TYPE arg2), void (*printFunc)(ELEMENT_TYPE arg))
{
    /*回调函数——比较*/
    m_compareFunc = compareFunc;
    /*回调函数——打印*/
    m_printFunc = printFunc;
    /*空树*/
    m_root = NULL;
    m_size = 0;
}

/*析构函数*/
BinaryTree::~BinaryTree()
{
}

/*更新节点高度*/
void BinaryTree::updateNodeHeight(BinaryTreeNode *node)
{
    /*左子树高度*/
    int leftHeight = node->m_left != NULL ? node->m_left->m_height : 0;
    /*右子树高度*/
    int rightHeight = node->m_right != NULL ? node->m_right->m_height : 0;
    int newHeight = 0;
    if (leftHeight > rightHeight)
    {
        newHeight = leftHeight + 1;
    }
    else
    {
        newHeight = rightHeight + 1;
    }
}
/*获取节点的平衡因子*/
int BinaryTree::getBalanceFactor(BinaryTreeNode *node)
{
    int leftHeight = node->m_left != NULL ? node->m_left->m_height : 0;
    int rightHeight = node->m_right != NULL ? node->m_right->m_height : 0;
    return leftHeight - rightHeight;
}
/* 判断节点是否平衡 */
bool BinaryTree::isBalanced(BinaryTreeNode *node)
{
    return abs(getBalanceFactor(node)) <= 1;
}

/*调整平衡*/
void BinaryTree::adjustBalance(BinaryTreeNode *node)
{
    /* LL,LR,RL,RR */
    BinaryTreeNode *parent = getTallerNode(node);
    BinaryTreeNode *child = getTallerNode(parent);
    if (IsLeft(parent) == true)
    {
        /* LX */
        if (IsLeft(child) == true)
        {
            /* LL */
        }
        else
        {
            /* LR */
        }
    }
    else if (IsRight(parent) == true)
    {
        /* RX */
        if (IsLeft(child) == true)
        {
            /* RL */
        }
        else
        {
            /* RR */
        }
    }
}

/*得到某节点较高的子节点 */
BinaryTreeNode *BinaryTree::getTallerNode(BinaryTreeNode *node)
{
    int leftHeight = node->m_left != NULL ? node->m_left->m_height : 0;
    int rightHeight = node->m_right != NULL ? node->m_right->m_height : 0;

    if (leftHeight > rightHeight)
    {
        return node->m_left;
    }
    else
    {
        return node->m_right;
    }
}

/*左旋*/
void BinaryTree::leftRotate(BinaryTreeNode *grand)
{
    BinaryTreeNode *parent = grand->m_right;
    BinaryTreeNode *child = parent->m_left;
    grand->m_right = parent->m_left;    // 1
    parent->m_left = grand;             // 2
    parent->m_parent = grand->m_parent; // 3
    if (IsLeft(grand) == true)
    {
        grand->m_parent->m_left = parent; // 4
    }
    else if (IsRight(grand) == true)
    {
        grand->m_parent->m_right = parent; // 4
    }
    if (child != NULL)
    {
        child->m_parent = grand;
    }

    /*更新高度 */
    updateNodeHeight(grand);
    updateNodeHeight(parent);
}
/*右旋*/
void BinaryTree::rightRotate(BinaryTreeNode *grand)
{
    BinaryTree *parent = grand->m_left;
    BinaryTree *child = parent->m_right;

    grand->m_left = child;   // 1
    parent->m_right = grand; // 2

    parent->m_parent = grand->m_parent; // 3
    if (IsLeft(grand))
    {
        grand->m_parent->m_left = parent; // 4
    }
    else if (IsLeft(grand))
    {
        grand->m_parent->m_right = parent; // 4
    }
    else
    {
        /*根节点*/
        m_root = parent; // 4
    }
    grand->m parent = parent; // 5
    if (child != NULL) 
    {
        child->m_parent = grand; // 6
    }
    /*更新高度 */
    updateNodeHeight(grand);
    updateNodeHeight(parent);
}

/*插入节点之后 */
void BinaryTree::insertAfter(BinaryTreeNode *node)
{
    while ((node = node->m_parent) != NULL)
    {
        /* 判断node节点是否平衡 */
        if (isBalanced(node) == true)
        {
            updateNodeHeight(node);
        }
        else
        {
            /*不平衡*/
            /* node是第一个不平衡节点。*/
            adjustBalance(node);
            break;
        }
    }
}

/*插入数据*/
void BinaryTree::insertData(ELEMENT_TYPE data)
{
    BinaryTreeNode *newNode = new BinaryTreeNode(data, NULL, NULL, NULL);
    if (m_root == NULL)
    {
        m_root = newNode;
        /*树元素个数++*/
        m_size++;
        return;
    }
    BinaryTreeNode *travelNode = m_root;
    BinaryTreeNode *backupNode = travelNode;
    int cmp = 0;
    while (travelNode != NULL)
    {

        cmp = m_compareFunc(data, travelNode->m_data);
        backupNode = travelNode;
        if (cmp < 0)
        {
            travelNode = travelNode->m_left;
        }
        else if (cmp > 0)
        {
            travelNode = travelNode->m_right;
        }
        else
        {
            return;
        }
    }
    /*退出循环说明：travelNode就是我要插入的位置*/
    if (cmp < 0)
    {
        backupNode->m_left = newNode;
    }
    else if (cmp > 0)
    {
        backupNode->m_right = newNode;
    }
    else
    {
        return;
    }
    /*树元素个数++*/
    m_size++;

    return;
}

bool BinaryTree::isContainData(ELEMENT_TYPE data) // 是否包含某个元素
{
    return getAppointNode(data) != NULL;
}

void BinaryTree::levelTravel()
{
    /*空树*/
    if (m_root == NULL)
    {
        return;
    }

    Queue myqueue;
    /*将根节点人队*/
    myqueue.push((void *)m_root);

    while (myqueue.isEmpty() == false)
    {
        /*取出队头元素*/
        BinaryTreeNode *topval = (BinaryTreeNode *)myqueue.front();
        /*定义对头函数*/
        m_printFunc(topval->m_data);
        myqueue.pop();
        /*将左子树入队*/
        if (topval->m_left != NULL)
        {
            myqueue.push(topval->m_left);
        }
        /*将右子树*/
        if (topval->m_right != NULL)
        {
            myqueue.push(topval->m_right);
        }
    }
}

/*度为2 */
bool BinaryTree::hasTwochildren(BinaryTreeNode *node)
{
    return node->m_left != NULL && node->m_right != NULL;
}
/*度为1 */
bool BinaryTree::hasOnechildren(BinaryTreeNode *node)
{
    return (node->m_left != NULL && node->m_right == NULL) || (node->m_left == NULL && node->m_right != NULL);
}
/*度为0(叶子结点)*/
bool BinaryTree::isLeaf(BinaryTreeNode *node)
{
    return node->m_left == NULL && node->m_right == NULL;
}
/*根据指定的值得到树的结点*/
BinaryTreeNode *BinaryTree::getAppointNode(ELEMENT_TYPE data)
{
    BinaryTreeNode *travelNode = m_root;
    int cmp = 0;
    while (travelNode != NULL)
    {
        cmp = m_compareFunc(data, travelNode->m_data);
        if (cmp == 0)
        {
            return travelNode;
        }
        else if (cmp < 0)
        {
            travelNode = travelNode->m_left;
        }
        else if (cmp > 0)
        {
            travelNode = travelNode->m_right;
        }
    }
    return NULL;
}

// 前驱节点
BinaryTreeNode *BinaryTree::getPreDecessor(BinaryTreeNode *node)
{
    /*判断节点是否有左子树 */
    BinaryTreeNode *travelNode = NULL;
    if (node->m_left != NULL)
    {
        travelNode = node->m_left;
        while (travelNode->m_right != NULL)
        {
            travelNode = travelNode->m_right;
        }
        return travelNode;
    }
    // 程序执行到这里 是意味着结点没有左子树，
    // 对于没有左子树的情况:向父节点找,向祖父节点找,向祖先节点找....
    travelNode = node;
    while (travelNode->m_parent != NULL && travelNode == travelNode->m_left)
    {
        travelNode = travelNode->m_parent;
    }
    return travelNode->m_parent;
}

// 后继节点
BinaryTreeNode *BinaryTree::getSuccessor(BinaryTreeNode *node)
{
    return nullptr;
}

bool BinaryTree::IsLeft(BinaryTreeNode *node)
{
    return node->m_parent != NULL && node == node->m_parent->m_left;
}

bool BinaryTree::IsRight(BinaryTreeNode *node)
{
    return node->m_parent != NULL && node == node->m_parent->m_right;
}

// 删除数据
void BinaryTree::deleteData(ELEMENT_TYPE data)
{
    // 根据值找到节点
    BinaryTreeNode *delNode = getAppointNode(data);
    // 判断节点的度
    if (hasTwochildren(delNode) == true)
    {
        /* 度为2 */

        /*找到前驱结点 */
        BinaryTreeNode *preNode = getPreDecessor(delNode);

        /*复制前驱结点的值 到 要删除的结点 */
        delNode->m_data = preNode->m_data;
        delNode = preNode;
    }
    /*程序到这里:一定意味着该节点度为1 或者 度为0.*/

    /*假设度为1.*/
    BinaryTreeNode *childNode = delNode->m_left != NULL ? delNode->m_left : delNode->m_right;

    if (childNode != NULL)
    {
        if (delNode->m_parent != NULL)
        {
            if (IsLeft(delNode) == true)
            {
                delNode->m_parent->m_left = childNode;
            }
            else if (IsRight(delNode) == true)
            {
                delNode->m_parent->m_right = childNode;
            }
            childNode->m_parent = delNode->m_parent;
            /*释放堆空间。*/
            if (delNode != NULL)
            {
                delete delNode;
                delNode = NULL;
            }
        }
        else
        {
            /*度为1 & 且根节点 */
            m_root = childNode;
            /*释放堆空间.*/
            if (delNode != NULL)
            {
                delete delNode;
                delNode = NULL;
            }
        }
    }
    else
    {
        /* 度为0 */
        if (delNode->m_parent != NULL)
        {
            if (IsLeft(delNode) == true)
            {
                delNode->m_parent->m_left = NULL;
                /*释放堆空间.*/
                if (delNode != NULL)
                {
                    delete delNode;
                    delNode = NULL;
                }
            }
        }
        else
            /*度为0 & 且为根节点。*/
            m_root = NULL;
        /*释放堆空间.*/
        if (delNode != NULL)
        {
            delete delNode;
            delNode = NULL;
        }
    }
    m_size--;

    return;
}

void BinaryTree::preOrder(BinaryTreeNode *travelNode)
{
    if (travelnode == NULL)
    {
        return;
    }
    m_printFunc(travelnode->m_data);
    preOrder(travelnode->m_left);  // 遍历左子树
    preOrder(travelnode->m_right); // 遍历右子树
}

void BinaryTree::inorder(BinaryTreeNode *travelNode)
{
    if (travelnode == NULL)
    {
        return;
    }

    preOrder(travelnode->m_left); // 遍历左子树
    m_printFunc(travelnode->m_data);
    preOrder(travelnode->m_right); // 遍历右子树
}

void BinaryTree::postorder(BinaryTreeNode *travelNode)
{
}

void BinaryTree::preOrderTravel() // 前序遍历
{
}

void BinaryTree::inorderTravel() // 中序遍历
{
}

void BinaryTree::postorderTravel() // 后序遍历
{
}
